package class06;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Auther: xw
 * @Create: 2022/3/25 14:30
 * @Description: K个有序链表排序   // 测试链接：https://leetcode.com/problems/merge-k-sorted-lists/
 */
public class mergeKSortedList {
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static class ListNodeComparator implements Comparator<ListNode> {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }

    public static ListNode mergeSortedList(ListNode[] lists){
        if(null == lists){
            return null;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                heap.add(lists[i]);
            }
        }
        if(heap.isEmpty()){
            return null;
        }
        ListNode head = heap.poll();
        ListNode pre = head;
        if(pre.next != null){
            heap.add(pre.next);
        }
        while (!heap.isEmpty()) {
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = cur;
            if (cur.next != null) {
                heap.add(cur.next);
            }
        }
        return head;

    }

}
